package graph2;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Author yuh
 * @Date Created in 上午7:58 2018/4/3
 * @Description 稠密图 用临接矩阵表示
 */
public class DenseGraph implements Graph {
    /**
     * 节点
     */
    private int v;
    /**
     * 边
     */
    private int m;
    /**
     * 矩阵
     */
    private boolean[][] matrix;
    /**
     * 是否有向
     */
    private boolean directed;

    public DenseGraph(int v, boolean directed) {
        this.directed = directed;
        this.v = v;
        this.m = 0;
        matrix = new boolean[v][v];
        for (int i = 0; i < matrix.length; i++) {
            matrix[i] = new boolean[v];
        }
    }

    /**
     * 几个顶点
     *
     * @return
     */
    @Override
    public int V() {
        return v;
    }

    /**
     * 几条边
     *
     * @return
     */
    @Override
    public int E() {
        return m;
    }

    /**
     * 两个顶点之间是否有边
     *
     * @param v
     * @param w
     * @return
     */
    @Override
    public boolean hasEdge(int v, int w) {
        return matrix[v][w];
    }

    /**
     * 给定两个顶点添加一条边
     *
     * @param v
     * @param w
     */
    @Override
    public void addEdge(int v, int w) {
        if (hasEdge(v, w)) {
            return;
        }

        matrix[v][w] = true;
        if (!directed) {
            matrix[w][v] = true;
        }
        m++;
    }

    /**
     * 打印整个连接情况
     */
    @Override
    public void show() {
        for (int i = 0; i < matrix.length; i++) {
            System.out.println(Arrays.toString(matrix[i]));
        }
    }

    /**
     * 打印和这个顶点关联的所有的边
     *
     * @param v
     * @return
     */
    @Override
    public Iterable<Integer> adj(int v) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        boolean[] sub = this.matrix[v];
        for (int i = 0; i < sub.length; i++) {
            if (sub[i]) {
                linkedList.add(i);
            }
        }
        return linkedList;
    }
}
